package 程序员面试金典;

import java.nio.charset.IllegalCharsetNameException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 迷路的机器人 {

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        List<List<Integer>> lists = new LinkedList<>();
        dfs(obstacleGrid,lists,0,0);
        return lists;
    }

    private boolean dfs(int[][] obstacleGrid, List<List<Integer>> lists, int x, int y) {
        //判断是否越界
        if (x<0 || x>=obstacleGrid.length || y<0 || y>=obstacleGrid[0].length || obstacleGrid[x][y]==1)
            return false;
        //设置为已访问过
        obstacleGrid[x][y]=1;
        lists.add(Arrays.asList(x,y));
        //到达终点
        if (x==obstacleGrid.length-1 && y==obstacleGrid[0].length-1)
            return true;
        //判断向左是否可以到达终点
        if (dfs(obstacleGrid,lists,x+1,y))
            return true;
        //判断向下是否可以到达终点
        if (dfs(obstacleGrid,lists,x,y+1))
            return true;
        //如果都不可以，则将该坐标从列表中删除
        lists.remove(lists.size()-1);
        return false;
    }
}
